<!--
 * @Author: your name
 * @Date: 2021-08-03 17:52:37
 * @LastEditTime: 2021-08-09 17:05:40
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>希尔排序</title>
</head>

<body>
  <img src="../images/shellSort.jpg" alt="">
  <p>将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述</p>
  <p>选择一个增量序列t1，t2，…，tk，其中t1>t2>...，tk=1；</p>
  <p>按增量序列个数k，对序列进行k 趟排序</p>
  <p>每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。</p>

  <script>
    function shellSort(array) {
      // 1. 获取数组的长度
      var length = array.length

      // 2. 初始化的增量(间隔)
      var gap = Math.floor(length / 2)
      

      // 3. while循环(gap不断的缩小)
      while (gap >= 1) {
        // 4. 以gap作为间隔进行分组，对分组进行插入排序
        for (var i = gap; i < length; i++) {// gap = 3
          var temp = array[i]
          var j = i
          console.log(array[j - gap], array[j] , 'gap', gap)
          while (array[j - gap] > temp && j > gap - 1) {
            
            array[j] = array[j - gap]
            j -= gap
          }

          // 5. 将j位置的元素赋值temp
          array[j] = temp
        }

        // 6. 增量变化 / 2
        gap = Math.floor(gap / 2)
      }

      return array
    }

    /**
     * 第一轮 gap = 5
     * 3 和 33 比较大小，不需要交换位置
     * 6 和 99 比较大小，不需要交换位置
     * 1 和 22 比较大小，不需要交换位置
     * 2 和 71 比较大小，不需要交换位置
     * 56 和 32 比较大小，需要交换位置
     * 33 和 55 比较大小，不需要交换位置
     * 第一轮的后数组结果为：[3, 6, 1, 2, 32, 33, 99, 22, 71, 56, 55]
     * 第二轮 gap = 2 
     * 3 和 1 比较大小，交换位置，[1, 6, 3, 2, 32, 33, 99, 22, 71, 56, 55]
     * 6 和 2 比较大小，交换位置，[1, 2, 3, 6, 32, 33, 99, 22, 71, 56, 55]
     * 3 和 32 比较大小，不交换位置，
     * 6 和 33 比较大小，不交换位置
     * 32 和 99 比较大小，不交换位置
     * 33 和 22 比较大小，交换位置，[1, 6, 3, 2, 32, 22, 99, 33, 71, 56, 55]
     * 99 和 71 比较大小，交换位置，[1, 6, 3, 2, 32, 22, 71, 33, 99, 56, 55]
     * 33 和 56 比较大小，不交换位置
     * 99 和 55 比较大小，交换位置，[1, 6, 3, 2, 32, 22, 71, 33, 55, 56, 99]
     * 
     * 第二轮的后数组结果为：[1, 2, 3, 6, 32, 22, 71, 33, 55, 56, 99]
     * 第三轮gap = 1
     * 做一次插入排序后结束
     * 最后排序结果，[1, 2, 3, 6, 22, 32, 33, 55, 56, 71, 99]
     */

    console.log(shellSort([3, 6, 1, 2, 56, 33, 99, 22, 71, 32, 55]))
  </script>
</body>

</html>